/LMAR=0/XLINE=3/FONT#0=BAXL30/FONT#1=BAXM30/FONT#2=BASB30/FONT#3=SUB/FONT#4=SUP/FONT#5=BASL35/FONT#6=NGR25/FONT#7=MATH30/FONT#8=FIX25



␈↓ α∧␈↓α␈↓ α↔MINIMAL ENTAILMENT - A MODE OF REASONING RELATED TO OCCAM'S RAZOR

␈↓ α∧␈↓␈↓ αTLet␈α
␈↓↓A␈↓␈α
be␈αa␈α
set␈α
of␈αsentences␈α
of␈α
first␈α
order␈αlogic␈α
and␈α
␈↓↓p␈↓␈αa␈α
sentence.␈α
 We␈αsay␈α
that␈α
␈↓↓A␈↓␈α
entails␈α␈↓↓p␈↓
␈↓ α∧␈↓(written␈α␈↓↓A␈α␈↓πq␈↓↓␈αp␈↓)␈αiff␈α␈↓↓p␈↓␈αis␈αtrue␈αin␈αall␈αmodels␈αof␈α␈↓↓A.␈↓␈αSuppose␈α␈↓↓M1␈↓␈αand␈α␈↓↓M2␈↓␈αare␈αtwo␈αmodels␈αof␈αa␈αset␈αof
␈↓ α∧␈↓sentences␈αin␈α
a␈αmulti-sorted␈α
logic.␈α We␈α
say␈αthat␈α␈↓↓M2␈↓␈α
extends␈α␈↓↓M1␈↓␈α
(written␈α␈↓↓M1␈α
≤␈αM2␈↓)␈αiff␈α
␈↓↓domain(M1)
␈↓ α∧␈↓↓⊂␈α∂domain(M2)␈↓,␈α∂but␈α∂the␈α∂predicates␈α∂when␈α∂applied␈α∂to␈α∂the␈α∂elements␈α∂of␈α∂␈↓↓domain(M1)␈↓␈α∂have␈α∂the␈α∞same
␈↓ α∧␈↓values␈α∞in␈α∞␈↓↓M2␈↓␈α∞that␈α∞they␈α∂have␈α∞in␈α∞␈↓↓M1.␈↓␈α∞␈↓↓M␈↓␈α∞is␈α∂called␈α∞a␈α∞minimal␈α∞model␈α∞of␈α∂␈↓↓A␈↓␈α∞iff␈α∞it␈α∞is␈α∞not␈α∂a␈α∞proper
␈↓ α∧␈↓extension␈α
of␈α
another␈α
model.␈α
 We␈α
say␈α
that␈α
␈↓↓A␈↓␈α
␈↓↓minimally␈α
entails␈α
p␈↓␈α
(written␈α
␈↓↓A␈α
␈↓πq␈↓βm␈↓↓␈α
p␈↓)␈α
iff␈α
␈↓↓p␈↓␈α
is␈α
true␈α
in␈α
all
␈↓ α∧␈↓minimal models of ␈↓↓A.␈↓

␈↓ α∧␈↓␈↓ αTWe␈α⊂propose␈α⊂to␈α⊂show␈α⊂that␈α⊂minimal␈α⊂entailment␈α⊂is␈α⊂a␈α⊂useful␈α⊂mode␈α⊂of␈α⊂reasoning␈α⊂but␈α⊃is␈α⊂not
␈↓ α∧␈↓equivalent␈α
to␈αany␈α
form␈αof␈α
deduction.␈α The␈α
latter␈αis␈α
easy.␈α For␈α
any␈αform␈α
of␈αdeduction,␈α
if␈α␈↓↓A␈α
␈↓πr␈↓↓␈αp␈↓␈α
and
␈↓ α∧␈↓␈↓↓A␈α
⊂␈α
B␈↓,␈α
then␈α
␈↓↓B␈α
␈↓πr␈↓↓␈αp␈↓.␈α
 We␈α
may␈α
call␈α
this␈α
property␈α␈↓↓monotonicity␈↓.␈α
 Exactly␈α
the␈α
same␈α
proof␈α
that␈αproved␈α
␈↓↓p␈↓
␈↓ α∧␈↓from␈α␈↓↓A␈↓␈αwill␈αprove␈αit␈αfrom␈α␈↓↓B.␈↓␈αEntailment␈αalso␈αhas␈αthis␈αproperty;␈αif␈α␈↓↓p␈↓␈αis␈αtrue␈αin␈αall␈αmodels␈αof␈α␈↓↓A,␈↓␈αit
␈↓ α∧␈↓is␈αtrue␈αin␈αall␈αmodels␈αof␈α␈↓↓B,␈↓␈αbecause␈αthe␈αlatter␈αare␈αa␈αsubset␈αof␈αthe␈αmodels␈αof␈α␈↓↓A.␈↓␈αHowever,␈αminimal
␈↓ α∧␈↓entailment␈αis␈α
not␈αmonotonic.␈α
 Namely,␈αconsider␈α
the␈αnull␈αset␈α
␈↓↓N␈↓␈αof␈α
sentences.␈α Its␈α
minimal␈αmodel␈αis␈α
a
␈↓ α∧␈↓domain␈α∂with␈α∂one␈α∂element␈α∂(in␈α∂most␈α⊂formalizations)␈α∂so␈α∂that␈α∂the␈α∂sentence␈α∂␈↓↓∀x y.x = y␈↓␈α⊂is␈α∂minimally
␈↓ α∧␈↓entailed␈α
by␈α
␈↓↓N.␈↓␈α
However,␈α
the␈α
set␈α
␈↓↓B␈↓␈α
consisting␈α
of␈α
the␈α
negation␈α
of␈α
this␈α
sentence␈α
certainly␈α
contains␈α
the
␈↓ α∧␈↓null set ␈↓↓N.␈↓ Less trivial examples can be constructed.

␈↓ α∧␈↓␈↓ αTWe␈α
don't␈α
propose␈α
minimal␈α
entailment␈α
as␈αa␈α
conclusive␈α
mode␈α
of␈α
reasoning.␈α
 However,␈αwhen
␈↓ α∧␈↓we␈α
have␈α
a␈α
set␈α␈↓↓A␈↓␈α
of␈α
facts,␈α
we␈α
often␈αjump␈α
to␈α
the␈α
conclusion␈α
or␈αat␈α
least␈α
conjecture␈α
that␈αthese␈α
(together
␈↓ α∧␈↓with␈α∂common␈α⊂sense␈α∂knowledge)␈α∂are␈α⊂all␈α∂the␈α∂relevant␈α⊂facts,␈α∂and␈α∂we␈α⊂try␈α∂to␈α∂construct␈α⊂the␈α∂simplest
␈↓ α∧␈↓theory consistent with these facts.  This is the connection with Occam's razor.

␈↓ α∧␈↓␈↓ αTAn␈α∩example␈α∩that␈α∩has␈α∩been␈α∩much␈α∩studied␈α⊃in␈α∩AI␈α∩and␈α∩which␈α∩contains␈α∩enough␈α∩detail␈α⊃to
␈↓ α∧␈↓illustrate various issues is the ␈↓↓missionaries and cannibals␈↓ problem, stated as follows:

␈↓ α∧␈↓␈↓ αT␈↓↓"Three␈α∪missionaries␈α∀and␈α∪three␈α∀cannibals␈α∪come␈α∀to␈α∪a␈α∪river.␈α∀ A␈α∪rowboat␈α∀that␈α∪seats␈α∀two␈α∪is
␈↓ α∧␈↓↓available.␈α
 However,␈αif␈α
the␈αcannibals␈α
ever␈αoutnumber␈α
the␈αmissionaries␈α
on␈αeither␈α
bank␈αof␈α
the␈αriver,
␈↓ α∧␈↓↓the outnumbered missionaries will be eaten.  How shall they cross the river?"␈↓.

␈↓ α∧␈↓␈↓ αTAmarel␈α⊃(1971)␈α⊃considered␈α⊃various␈α⊃representations␈α⊃of␈α⊃the␈α⊃problem␈α⊃and␈α∩discussed␈α⊃criteria
␈↓ α∧␈↓whereby␈α⊂the␈α⊃following␈α⊂representation␈α⊂is␈α⊃preferred␈α⊂for␈α⊂purposes␈α⊃of␈α⊂AI,␈α⊂because␈α⊃it␈α⊂leads␈α⊃to␈α⊂the
␈↓ α∧␈↓smallest␈αstate␈αspace␈αthat␈αmust␈αbe␈αexplored␈αto␈αfind␈αthe␈αsolution.␈α We␈αrepresent␈αa␈αstate␈αby␈αthe␈α
triplet
␈↓ α∧␈↓consisting␈α∞of␈α∞the␈α
numbers␈α∞of␈α∞missionaries,␈α
cannibals␈α∞and␈α∞boats␈α
on␈α∞the␈α∞initial␈α
bank␈α∞of␈α∞the␈α
river.
␈↓ α∧␈↓The␈αinitial␈αconfiguration␈α
is␈α331,␈αthe␈αdesired␈α
final␈αconfiguration␈αis␈α000,␈α
and␈αone␈αsolution␈α
is␈αgiven
␈↓ α∧␈↓by (331,220,321,300,311,110,221,020,031,010,021,000).

␈↓ α∧␈↓␈↓ αTWe␈α
are␈αinterested␈α
in␈αthe␈α
correctness␈αof␈α
the␈αreasoning␈α
that␈αgoes␈α
from␈αthe␈α
English␈αstatement
␈↓ α∧␈↓of␈αthe␈αproblem␈αto␈αthe␈αabove␈αstate␈αspace␈αrepresentation.␈α Suppose␈αthe␈αEnglish␈αsentences␈αdescribing
␈↓ α∧␈↓the␈α⊗problem␈α∃have␈α⊗already␈α∃been␈α⊗rather␈α⊗directly␈α∃translated␈α⊗into␈α∃first␈α⊗order␈α⊗logic.␈α∃ Amarel's
␈↓ α∧␈↓representation␈α∞cannot␈α∞be␈α∞␈↓↓deduced␈↓␈α∂from␈α∞these␈α∞sentences␈α∞for␈α∂two␈α∞reasons.␈α∞ First␈α∞nothing␈α∂has␈α∞been
␈↓ α∧␈↓stated␈α
about␈αthe␈α
properties␈αof␈α
boats␈αor␈α
even␈α
the␈αfact␈α
that␈αrowing␈α
across␈αthe␈α
river␈α
doesn't␈αchange
␈↓ α∧␈↓the␈αnumbers␈αof␈αmissionaries␈αor␈αcannibals␈αor␈αthe␈αcapacity␈αof␈αthe␈αboat.␈α These␈αare␈αa␈αconsequence␈α
of
␈↓ α∧␈↓common␈αsense␈αknowledge,␈αso␈αlet␈αus␈αimagine␈αthat␈αcommon␈αsense␈αknowledge,␈αor␈αat␈αleast␈αthe␈αrelevant
␈↓ α∧␈↓part of it, is also expressed in first order logic.


␈↓ α∧␈↓␈↓ ε|1␈↓ ∧



␈↓ α∧␈↓␈↓ αTThe␈α∩second␈α⊃reason␈α∩we␈α⊃can't␈α∩␈↓↓deduce␈↓␈α∩the␈α⊃propriety␈α∩of␈α⊃Amarel's␈α∩representation␈α∩is␈α⊃deeper.
␈↓ α∧␈↓Imagine␈α
giving␈α
someone␈α
the␈α
problem,␈α
and␈α
after␈αhe␈α
puzzles␈α
for␈α
a␈α
while,␈α
he␈α
suggests␈αgoing␈α
upstream
␈↓ α∧␈↓half␈α
a␈α
mile␈α
and␈α
crossing␈α
on␈α
a␈α
bridge.␈α∞ "What␈α
bridge",␈α
you␈α
say.␈α
 "No␈α
bridge␈α
is␈α
mentioned␈α∞in␈α
the
␈↓ α∧␈↓statement␈αof␈αthe␈α
problem."␈αAnd␈αthis␈α
dunce␈αreplies,␈α"Well,␈α
it␈αisn't␈αstated␈α
that␈αthere␈αisn't␈α
a␈αbridge".
␈↓ α∧␈↓You␈αlook␈αat␈αthe␈αEnglish␈αand␈αeven␈αat␈αthe␈αtranslation␈αof␈αthe␈αEnglish␈αinto␈αfirst␈αorder␈αlogic,␈αand␈αyou
␈↓ α∧␈↓must␈α
admit␈α∞that␈α
it␈α
isn't␈α∞stated␈α
that␈α
there␈α∞is␈α
no␈α
bridge.␈α∞ So␈α
you␈α
modify␈α∞the␈α
problem,␈α
and␈α∞pose␈α
it
␈↓ α∧␈↓again,␈α∂and␈α∂the␈α∂dunce␈α⊂proposes␈α∂a␈α∂helicopter,␈α∂and␈α∂after␈α⊂you␈α∂exclude␈α∂that␈α∂he␈α∂proposes␈α⊂a␈α∂winged
␈↓ α∧␈↓horse␈α
or␈αthat␈α
the␈αothers␈α
hang␈αonto␈α
the␈αoutside␈α
of␈αthe␈α
boat␈αwhile␈α
two␈αrow.␈α
 You␈αnow␈α
see␈αthat␈α
while
␈↓ α∧␈↓a␈α
dunce,␈α
he␈α
is␈αan␈α
inventive␈α
dunce,␈α
and␈α
you␈αdespair␈α
of␈α
getting␈α
him␈αto␈α
accept␈α
the␈α
problem␈α
in␈αthe
␈↓ α∧␈↓proper␈αpuzzler's␈αspirit␈αand␈α
tell␈αhim␈αthe␈αsolution.␈α You␈α
are␈αfurther␈αannoyed␈αwhen␈αhe␈α
attacks␈αyour
␈↓ α∧␈↓solution␈α
on␈α∞the␈α
grounds␈α
that␈α∞the␈α
boat␈α∞might␈α
not␈α
have␈α∞oars.␈α
 After␈α
you␈α∞rectify␈α
that␈α∞omission,␈α
he
␈↓ α∧␈↓suggests␈α∞that␈α∞a␈α∞sea␈α∞monster␈α∞may␈α∞swim␈α∞up␈α∞the␈α∞river␈α∞and␈α∞may␈α∞swallow␈α∞the␈α∞boat.␈α∞ Again␈α∞you␈α∞are
␈↓ α∧␈↓frustrated, and you look for a mode of reasoning that will settle his hash once and for all.

␈↓ α∧␈↓␈↓ αTMinimal␈αmodels␈αand␈αminimal␈αentailment␈αmay␈αgive␈αthe␈αsolution.␈α In␈αa␈αminimal␈αmodel␈αof␈αthe
␈↓ α∧␈↓first␈α∞order␈α
logic␈α∞statement␈α
of␈α∞the␈α
problem,␈α∞there␈α∞is␈α
no␈α∞bridge␈α
or␈α∞helicopter.␈α
 "Ah",␈α∞you␈α∞say,␈α
"but
␈↓ α∧␈↓there␈αaren't␈αany␈αoars␈αeither".␈α No,␈αwe␈αget␈αout␈αof␈αthat␈αas␈αfollows:␈αIt␈αis␈αa␈αpart␈αof␈αcommon␈αknowledge
␈↓ α∧␈↓that␈αa␈αboat␈αcan␈αbe␈αused␈αto␈αcross␈αa␈αriver␈α␈↓↓unless␈αthere␈αis␈αsomething␈αwrong␈αwith␈αit␈αor␈α
something␈αelse
␈↓ α∧␈↓↓prevents␈αusing␈αit␈↓,␈αand␈αin␈αthe␈αminimal␈αmodel␈αof␈αthe␈αfacts␈αthere␈αdoesn't␈αexist␈αsomething␈αwrong␈α
with
␈↓ α∧␈↓the boat, and there isn't anything else to prevent its use.

␈↓ α∧␈↓␈↓ αTThe␈α∩non-monotonic␈α∩character␈α∩of␈α⊃minimal␈α∩entailment␈α∩is␈α∩just␈α⊃what␈α∩we␈α∩want␈α∩here.␈α⊃ The
␈↓ α∧␈↓statement,␈α␈↓↓"There␈αis␈αa␈αbridge␈α
a␈αmile␈αupstream."␈↓␈αdoesn't␈αcontradict␈α
the␈αtext␈αof␈αthe␈αproblem,␈α
but␈αits
␈↓ α∧␈↓addition invalidates the Amarel representation.

␈↓ α∧␈↓␈↓ αTAt␈αfirst␈αI␈αconsidered␈αthis␈αsolution␈αtoo␈αad␈αhoc␈αto␈αbe␈αacceptable,␈αbut␈αI␈αam␈αnow␈αconvinced␈αthat
␈↓ α∧␈↓it␈αis␈αa␈αcorrect␈αexplication␈αof␈αthe␈α␈↓↓normal␈↓␈αsituation,␈αi.e.␈αunless␈αsomething␈αabnormal␈αexists,␈α
an␈αobject
␈↓ α∧␈↓can be used to carry out its normal function.

␈↓ α∧␈↓␈↓ αTThis␈α∞puts␈α∞a␈α∞burden␈α∞on␈α∞the␈α∞constructors␈α∞of␈α∞formal␈α∞systems␈α∞for␈α∞representing␈α∞common␈α
sense
␈↓ α∧␈↓knowledge.␈α Namely,␈α
we␈αmust␈αformalize␈α
such␈αabstractions␈α
as␈α"something␈αwrong␈α
with␈αthe␈α
boat".␈α I
␈↓ α∧␈↓believe we will have to accept this challenge.

␈↓ α∧␈↓␈↓ αTIt␈α∞has␈α∂been␈α∞suggested␈α∂that␈α∞the␈α∞difficulties␈α∂might␈α∞be␈α∂avoided␈α∞by␈α∂introducing␈α∞probabilities.
␈↓ α∧␈↓They␈α∞suggest␈α∞that␈α∞the␈α∂existence␈α∞of␈α∞a␈α∞bridge␈α∞is␈α∂improbable.␈α∞ Well␈α∞the␈α∞whole␈α∂situation␈α∞involving
␈↓ α∧␈↓cannibals␈α∩with␈α∩the␈α∩postulated␈α∩probabilities␈α∩is␈α∩sufficiently␈α∩improbable␈α∩that␈α∩it␈α∩is␈α∩hard␈α∩to␈α∩take
␈↓ α∧␈↓seriously␈α∂the␈α∂conditional␈α∂probability␈α∂of␈α∂a␈α∂bridge␈α∂given␈α∂the␈α∂hypotheses.␈α∂ Moreover,␈α⊂we␈α∂mentally
␈↓ α∧␈↓propose␈α⊂to␈α⊃ourselves␈α⊂the␈α⊃normal␈α⊂non-bridge␈α⊂non-sea␈α⊃monster␈α⊂interpretation␈α⊃␈↓↓before␈↓␈α⊂considering
␈↓ α∧␈↓these␈αextraneous␈αpossibilities,␈αlet␈αalone␈αtheir␈αprobabilities,␈αi.e.␈αwe␈αnever␈αeven␈αintroduce␈αthe␈αsample
␈↓ α∧␈↓space␈α
in␈α
which␈αthese␈α
possibilities␈α
are␈α
assigned␈αwhatever␈α
probabilities␈α
we␈α
might␈αeventually␈α
consider
␈↓ α∧␈↓them␈α∪to␈α∪have.␈α∪ Therefore,␈α∪regardless␈α∪of␈α∪our␈α∪knowledge␈α∪of␈α∪probabilities,␈α∪we␈α∪need␈α∪a␈α∀way␈α∪of
␈↓ α∧␈↓formulating␈α∂the␈α∂normal␈α∞situation␈α∂from␈α∂the␈α∂statement␈α∞of␈α∂the␈α∂facts,␈α∞and␈α∂minimal␈α∂models␈α∂seem␈α∞to
␈↓ α∧␈↓suggest how to solve the problem.






␈↓ α∧␈↓␈↓ ε|2␈↓ ∧



␈↓ α∧␈↓αMinimal models and minimal reasoning in propositional calculus.

␈↓ α∧␈↓␈↓ αTIn␈α⊃my␈α⊃present␈α⊂opinion,␈α⊃the␈α⊃technique␈α⊂of␈α⊃minimal␈α⊃entailment␈α⊂and␈α⊃the␈α⊃axiomatization␈α⊂of
␈↓ α∧␈↓common␈αsense␈αknowledge␈αin␈αa␈αform␈αsuitable␈αto␈αmake␈αuse␈αof␈αit␈αwill␈αboth␈αbe␈αdifficult.␈α Hopefully,␈αit
␈↓ α∧␈↓will␈α
repay␈αthe␈α
effort.␈α However,␈α
there␈αseems␈α
to␈α
be␈αa␈α
propositional␈αcalculus␈α
analog␈αof␈α
the␈αfirst␈α
order
␈↓ α∧␈↓logic␈α∞situation␈α∞that␈α∞may␈α∂be␈α∞easier␈α∞to␈α∞study␈α∂and␈α∞may␈α∞throw␈α∞some␈α∂light␈α∞on␈α∞the␈α∞main␈α∂problem.␈α∞ I
␈↓ α∧␈↓haven't yet found any direct applications of the propositional case, however.

␈↓ α∧␈↓␈↓ αTIn␈αpropositional␈αcalculus␈αwe␈αproceed␈αas␈αfollows.␈α Suppose␈αwe␈αhave␈αsome␈αfacts␈αto␈αexpress␈α
but
␈↓ α∧␈↓have␈αnot␈α
yet␈αchosen␈αa␈α
propositional␈αlanguage.␈α Our␈α
first␈αstep␈αis␈α
to␈αintroduce␈α
propositional␈αletters
␈↓ α∧␈↓␈↓↓p␈↓β1␈↓↓,...,p␈↓βn␈↓␈α∀and␈α∀to␈α∀specify␈α∀each␈α∀of␈α∀them␈α∀as␈α∀expressing␈α∀some␈α∀elementary␈α∀fact.␈α∀ We␈α∀call␈α∀this
␈↓ α∧␈↓establishing␈α∞a␈α
␈↓↓propositional␈α∞co-ordinate␈α∞system␈↓.␈α
 Then␈α∞we␈α
express␈α∞the␈α∞set␈α
␈↓↓A␈↓␈α∞of␈α
known␈α∞facts␈α∞as␈α
a
␈↓ α∧␈↓sentence␈α␈↓↓AX␈↓␈αin␈αthis␈αco-ordinate␈αsystem.␈α A␈αmodel␈α
of␈αthe␈αfacts␈αis␈αany␈αassignment␈αof␈αtruth␈αvalues␈α
to
␈↓ α∧␈↓the ␈↓↓p␈↓βi␈↓'s that makes ␈↓↓AX␈↓ true.  Let ␈↓↓M1␈↓ and ␈↓↓M2␈↓ be models of ␈↓↓AX.␈↓ We define

␈↓ α∧␈↓␈↓ αT␈↓↓M1 ≤ M2 ≡ ∀i.(true(p␈↓βi␈↓↓,M2) ⊃ true(p␈↓βi␈↓↓,M1))␈↓.

␈↓ α∧␈↓A␈α
minimal␈α
model␈α
is␈α
one␈α
that␈α
is␈α
not␈α
an␈α
extension,␈α
i.e.␈α
a␈α
model␈α
in␈α
which␈α
(roughly␈α
speaking)␈αas␈α
many
␈↓ α∧␈↓of␈αthe␈α␈↓↓p␈↓βi␈↓s␈αas␈αpossible␈αare␈αfalse␈α-␈αconsistent␈αwith␈αthe␈αtruth␈αof␈α␈↓↓AX␈↓.␈α ␈↓↓Note␈αthat␈αwhile␈αthe␈αmodels␈αof␈αa
␈↓ α∧␈↓↓set␈α⊂of␈α⊂facts␈α⊂are␈α⊂independent␈α⊂of␈α⊂the␈α⊂co-ordinate␈α⊂system,␈α⊂the␈α⊂minimal␈α⊂models␈α⊂depend␈α⊂on␈α⊂the␈α⊂co-
␈↓ α∧␈↓↓ordinate␈αsystem␈↓.␈α Here␈αis␈αthe␈αmost␈αtrivial␈αexample.␈α Let␈αthere␈αbe␈αone␈αletter␈α␈↓↓p␈↓␈αrepresenting␈αthe␈αone
␈↓ α∧␈↓fact␈α∞in␈α
a␈α∞co-ordinate␈α
system␈α∞␈↓↓C,␈↓␈α
and␈α∞let␈α
␈↓↓A␈↓␈α∞be␈α
the␈α∞null␈α
set␈α∞of␈α
facts␈α∞so␈α
that␈α∞␈↓↓AX␈↓␈α
is␈α∞the␈α∞sentence␈α
␈↓↓T␈↓
␈↓ α∧␈↓(identically␈α⊂true).␈α⊂ The␈α⊂one␈α⊂other␈α⊂co-ordinate␈α⊂system␈α⊂␈↓↓C'␈↓␈α⊂uses␈α⊂the␈α⊂elementary␈α⊂sentence␈α⊂␈↓↓p'␈↓␈α⊂taken
␈↓ α∧␈↓equivalent to ␈↓↓¬p␈↓.  The minimal model of ␈↓↓C␈↓ is {¬p}, and the minimal model of ␈↓↓C'␈↓ is {p}.

␈↓ α∧␈↓␈↓ αTA␈α∪less␈α∩trivial␈α∪example␈α∩of␈α∪minimal␈α∩entailment␈α∪is␈α∩the␈α∪following.␈α∩ The␈α∪propositional␈α∩co-
␈↓ α∧␈↓ordinate␈α
system␈α∞has␈α
basic␈α
sentences␈α∞␈↓↓p␈↓β1␈↓,␈α
␈↓↓p␈↓β2␈↓␈α
and␈α∞␈↓↓p␈↓β3␈↓,␈α
and␈α
␈↓↓AX␈α∞=␈α
p␈↓β1␈↓↓␈α
∨␈α∞p␈↓β2␈↓.␈α
 There␈α
are␈α∞two␈α
minimal
␈↓ α∧␈↓models.␈α
 ␈↓↓p␈↓β3␈↓␈α
is␈α
false␈αin␈α
both,␈α
and␈α
␈↓↓p␈↓β1␈↓␈αis␈α
false␈α
in␈α
one,␈αand␈α
␈↓↓p␈↓β2␈↓␈α
is␈α
false␈αin␈α
the␈α
other.␈α
 Thus␈α
we␈αhave
␈↓ α∧␈↓␈↓↓AX ␈↓πq␈↓βm␈↓↓ (¬(p␈↓β1␈↓↓ ∧ p␈↓β2␈↓↓) ∧ ¬p␈↓β3␈↓).

␈↓ α∧␈↓␈↓ αTNote␈α
that␈αif␈α
␈↓↓AX␈↓␈αis␈α
a␈α
conjunction␈αof␈α
certain␈αelementary␈α
sentences␈α
(some␈αof␈α
them␈αnegated),␈α
e.g.
␈↓ α∧␈↓␈↓↓AX = p␈↓β2␈↓↓ ∧ ¬p␈↓β4␈↓,␈α∂then␈α∂there␈α∂is␈α∂a␈α∂unique␈α∂minimal␈α∂model,␈α∂but␈α∂if,␈α∂as␈α∂above,␈α∂␈↓↓AX = p␈↓β2␈↓↓ ∨ ¬p␈↓β4␈↓,␈α∂then
␈↓ α∧␈↓there is more than one minimal model.

␈↓ α∧␈↓␈↓ αTImagine␈α
that␈α
we␈αdiscover␈α
a␈α
set␈α
of␈αfacts␈α
one␈α
at␈αa␈α
time␈α
so␈α
that␈αwe␈α
have␈α
an␈αincreasing␈α
sequence
␈↓ α∧␈↓␈↓↓A␈↓β1␈↓↓␈α⊂␈α
A␈↓β2␈↓␈α⊂␈α
...␈αof␈α
sets␈αof␈α
sentences.␈α A␈α
given␈αsentence␈α
␈↓↓p␈↓␈αmay␈α
oscillate␈αin␈α
its␈αminimal␈α
entailment␈αby
␈↓ α∧␈↓the␈α
␈↓↓A␈↓βi␈↓,␈α∞e.g.␈α
we␈α
may␈α∞have␈α
␈↓↓A␈↓β1␈↓π q␈↓βm␈↓↓ p␈↓,␈α∞␈↓↓A␈↓β2␈↓π q␈↓βm␈↓↓ ¬p␈↓,␈α
neither␈α
may␈α∞be␈α
entailed␈α
by␈α∞␈↓↓A␈↓β3␈↓,␈α
etc.␈α∞ The␈α
common
␈↓ α∧␈↓sense␈α⊂Occam's␈α⊂razor␈α⊂conclusion␈α⊃about␈α⊂a␈α⊂sentence␈α⊂␈↓↓p␈↓␈α⊂often␈α⊃behaves␈α⊂this␈α⊂way␈α⊂as␈α⊃our␈α⊂knowledge
␈↓ α∧␈↓increases.

␈↓ α∧␈↓␈↓ αTWe␈α∩hope␈α∪that␈α∩something␈α∪useful␈α∩may␈α∪be␈α∩learned␈α∪by␈α∩studying␈α∪the␈α∩logical␈α∪properties␈α∩of
␈↓ α∧␈↓propositional calculus minimal models and minimal entailment.







␈↓ α∧␈↓␈↓ ε|3␈↓ ∧



␈↓ α∧␈↓αNOTES

␈↓ α∧␈↓␈↓ αT1.␈α
There␈α
is␈α∞a␈α
relation␈α
between␈α∞minimal␈α
entailment␈α
and␈α∞the␈α
THNOT␈α
formalism␈α∞of␈α
micro-
␈↓ α∧␈↓planner.␈α (THNOT␈α␈↓↓p)␈↓␈αmeans␈αthat␈αan␈αattempt␈αto␈αprove␈α␈↓↓p␈↓␈αhas␈αfailed,␈αand␈αsuch␈αa␈αfailure␈α
to␈αprove
␈↓ α∧␈↓something␈αwrong␈αwith␈αthe␈αboat␈αcould␈αlead␈αto␈αa␈αplan␈αto␈αrow␈αaccross␈αthe␈αriver.␈α Likewise␈αfailure␈αto
␈↓ α∧␈↓prove the existence of a bridge can be used to go from the facts to the Amarel representation.

␈↓ α∧␈↓␈↓ αT2.␈α∂Note␈α∞that␈α∂minimal␈α∞entailment␈α∂is␈α∞a␈α∂semantic␈α∞idea.␈α∂ What␈α∞is␈α∂the␈α∂corresponding␈α∞syntactic
␈↓ α∧␈↓idea?␈α That␈α
is,␈αhow␈α
can␈αwe␈α
go␈αfrom␈α
the␈αset␈α
of␈αfirst␈α
order␈αlogic␈α
sentences␈αexpressing␈α␈↓↓missionary␈α
and
␈↓ α∧␈↓↓cannibals␈↓␈α
and␈α
the␈α
common␈α
sense␈α
axioms␈α
to␈α
the␈α
statement␈α
that␈α
there␈α
is␈α
no␈α
bridge␈α
and␈α
that␈αthere␈α
are
␈↓ α∧␈↓oars?␈α⊃ We␈α⊃want␈α⊃to␈α⊃proceed␈α⊃by␈α⊂some␈α⊃syntactic␈α⊃method␈α⊃using␈α⊃the␈α⊃sentences␈α⊃themselves␈α⊂without
␈↓ α∧␈↓considering␈α∂models.␈α∂ At␈α∂first␈α∞sight,␈α∂it␈α∂looks␈α∂like␈α∂we␈α∞should␈α∂adopt␈α∂the␈α∂micro-planner␈α∂method␈α∞of
␈↓ α∧␈↓trying␈αto␈αprove␈αthat␈αthere␈αis␈αa␈αbridge,␈αand,␈αfailing␈αin␈αthat,␈αassert␈αthat␈αthere␈αisn't.␈α There␈αmay␈αbe␈αa
␈↓ α∧␈↓better way.

␈↓ α∧␈↓John McCarthy
␈↓ α∧␈↓Artificial Intelligence Laboratory
␈↓ α∧␈↓Stanford University
␈↓ α∧␈↓Stanford, California 94305

␈↓ α∧␈↓␈↓εThis draft PUBbed at 17:30 on October 29, 1976.




























␈↓ α∧␈↓␈↓ ε|4␈↓ ∧